package 简单.模拟;

import java.util.Arrays;

/**
 * 给你一个长度固定的整数数组 arr，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。
 * 注意：请不要在超过该数组长度的位置写入元素。
 * 要求：请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/duplicate-zeros
 */
public class 复写零_1089 {

    public static void main(String[] args) {

        int[] arr = {9, 9, 9, 4, 8, 0, 0, 3, 7, 2, 0, 0, 0, 0, 9, 1, 0, 0, 1, 1, 0, 5, 6, 3, 1, 6, 0, 0, 2, 3, 4, 7, 0, 3, 9, 3, 6, 5, 8, 9, 1, 1, 3, 2, 0, 0, 7, 3, 3, 0, 5, 7, 0, 8, 1, 9, 6, 3, 0, 8, 8, 8, 8, 0, 0, 5, 0, 0, 0, 3, 7, 7, 7, 7, 5, 1, 0, 0, 8, 0, 0};
        duplicateZeros2(arr);
        System.out.println(Arrays.toString(arr));

    }

    /**
     * 模拟
     *
     * @param arr
     */
    public static void duplicateZeros(int[] arr) {
        int index = 0;
        while (index < arr.length - 1) {
            while (index < arr.length - 1 && arr[index] != 0) index++;
            if (index == arr.length - 1) break;
            int pre = arr[index + 1];
            arr[index + 1] = 0;
            for (int i = index + 2; i < arr.length; i++) {
                int cur = arr[i];
                arr[i] = pre;
                pre = cur;
            }
            index += 2;
        }
    }

    /**
     * 有多少个 0 ，右边就有几个数字被覆盖，
     * 那么先确定边界，使用双指针填充后面的数字，碰到 0 右边填充 2 个 0
     *
     * @param arr
     */
    public static void duplicateZeros2(int[] arr) {
        int countZero = 0;
        int left = 0, right = arr.length - 1;
        while (left < arr.length) {
            if (arr[left] == 0) countZero++;
            if (left + countZero >= arr.length - 1) break;
            left++;
        }
        // 如果分界是 0 可能存在，右边不需要用 2 个 0 填充的情况
        if (left + countZero > arr.length - 1) {
            arr[right] = 0;
            right--;
            left--;
        }

        while (left < right) {
            if (arr[left] == 0) {
                arr[right] = 0;
                arr[right - 1] = 0;
                right -= 2;
            } else {
                arr[right] = arr[left];
                right--;
            }
            left--;
        }
    }

}
